3.3 The Tabulation
Method
For Boolean functions of six or more variables,
the Map method is no longer convenient to use because of the excessive number
of squares that might present diffuculty in
recognizing certain patterns in order to get the
simplified logic expression.
The Tabulation method, also known as
Quine-McCluskey method, was developed to overcome this difficulty regarding the
use of map method.
This method requires a step-by-step process that
if followed correctly will result to a
guaranteed simplified logic expression.
Step1. List all minterms
that specify the function.
Step2. Find the prime implicants by using a
matching process.
Step3. Repeat the matching process until no
further elimination is possible.
Step4. The remaining terms and all the terms
that did not match during the process comprise the prime implicants.
Example no. 1
Simplify by using the Tabulation method.
F(w,x,y,z) = ∑ (0,1,2,8,10,11,14,15)
Solution no. 1
Step1. List all minterms
that specify the function according to the number of 1's
contained.
|
|
w |
x |
y |
z |
|
0 |
0 |
0 |
0 |
0 |
|
1 |
0 |
0 |
0 |
1 |
|
2 |
0 |
0 |
1 |
0 |
|
8 |
1 |
0 |
0 |
0 |
|
10 |
1 |
0 |
1 |
0 |
|
11 |
1 |
0 |
1 |
1 |
|
14 |
1 |
1 |
1 |
0 |
|
15 |
1 |
1 |
1 |
1 |
Step2. Any two minterms
that differ from each other by only one variable can be combined, and the
unmatched variable removed. A check (✓) is placed to the right
of both minterms toshow
that they have been used.
|
|
A |
|
|
B |
||||||
|
|
w |
x |
y |
z |
|
|
w |
x |
y |
z |
|
0 |
0 |
0 |
0 |
0 |
✓ |
0,1 |
0 |
0 |
0 |
- |
|
1 |
0 |
0 |
0 |
1 |
✓ |
0,2 |
0 |
0 |
- |
0 |
|
2 |
0 |
0 |
1 |
0 |
✓ |
0,8 |
- |
0 |
0 |
0 |
|
8 |
1 |
0 |
0 |
0 |
✓ |
2,10 |
- |
0 |
1 |
0 |
|
10 |
1 |
0 |
1 |
0 |
✓ |
8,10 |
1 |
0 |
- |
0 |
|
11 |
1 |
0 |
1 |
1 |
✓ |
10,11 |
1 |
0 |
1 |
- |
|
14 |
1 |
1 |
1 |
0 |
✓ |
10,14 |
1 |
- |
1 |
0 |
|
15 |
1 |
1 |
1 |
1 |
✓ |
11,15 |
1 |
- |
1 |
1 |
|
|
|
|
|
|
|
14,15 |
1 |
1 |
1 |
- |
Step3. The searching and comparing process is
repeated for the terms in column form the two-variable terms of column A.
|
|
B |
|
|
C |
||||||
|
|
w |
x |
y |
z |
|
|
w |
x |
y |
z |
|
0,1 |
0 |
0 |
0 |
- |
|
0,2,8,10 |
- |
0 |
- |
0 |
|
0,2 |
0 |
0 |
- |
0 |
✓ |
0,8,2,10 |
- |
0 |
- |
0 |
|
0,8 |
- |
0 |
0 |
0 |
✓ |
10,11,14,15 |
1 |
- |
1 |
- |
|
2,10 |
- |
0 |
1 |
0 |
✓ |
10,14,11,15 |
1 |
- |
1 |
- |
|
8,10 |
1 |
0 |
- |
0 |
✓ |
|
|
|
|
|
|
10,11 |
1 |
0 |
1 |
- |
✓ |
|
|
|
|
|
|
10,14 |
1 |
- |
1 |
0 |
✓ |
|
|
|
|
|
|
11,15 |
1 |
- |
1 |
1 |
✓ |
|
|
|
|
|
|
14,15 |
1 |
1 |
1 |
- |
✓ |
|
|
|
|
|
Step4. The unchecked terms in the table form the
prime implicants. From column B the term vxy (000-) and the terms x’z’
(-0-0) and wy (1-1-) from column C, thus the sum of
these terms gives the simplified expression for the function.
F= w'x'y' + x'z' + wy